package com.congee02;

public class TreeToDoublyList {

    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    };

    public Node treeToDoublyList(Node root) {

        final Node sentinel = new Node(-1000, null, root);
        Node add = sentinel;

        Node p = root;
        while (p != null) {
            Node step = successorBST(p, root);
            add.right = p;
            p.left = add;
            add = add.right;

            p = step;
        }

        return null;
    }

    private Node successorBST(Node node, Node root) {
        if (node == null) {
            return null;
        }
        if (node.left != null) {
            return findMostLeft(node.left);
        }
        System.out.println("found");
        Node ret = searchSuccessorFromRoot(node, root);
        System.out.println("f1");
        return ret;
    }

    private Node searchSuccessorFromRoot(Node node, Node root) {
        int x = node.val + 1;
        Node p = root;
        Node ret = null;
        while (p != null) {
            if (p.val == x) {
                return p;
            }
            if (p.val > x) {
                ret = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return ret;
    }

    private Node findMostLeft(Node node) {
        Node ret = node;
        while (ret.left != null) {
            ret = ret.left;
        }
        return ret;
    }

    public static void main(String[] args) {
        Node k = new Node(2);
        Node root = new Node(4);
        root.left = k;
        root.right = new Node(5);

        k.left = new Node(1);
        k.right = new Node(3);

        new TreeToDoublyList().treeToDoublyList(root);

    }

}
